home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 #2 / Ham Radio 2000 - Volume 2.iso / HAMV2 / TCP_IP / TNOS230S / RSPF.C < prev    next >
Encoding:
C/C++ Source or Header  |  1997-09-07  |  58.3 KB  |  1,944 lines
  1. /*             RSPF - Radio Shortest Path First
  2.  * This code may be used for non-commercial purposes only.
  3.  *            Anders Klemets SM0RGV
  4.  * 890918 - Version 2.0
  5.  * 900816 - Version 2.1
  6.  *
  7.  * Mods by PA0GRI
  8.  */
  9. #include "global.h"
  10. #include "mbuf.h"
  11. #include "proc.h"
  12. #include "netuser.h"
  13. #include "internet.h"
  14. #include "pktdrvr.h"
  15. #include "arp.h"
  16. #include "icmp.h"
  17. #include "rspf.h"
  18.  
  19. #if !defined(_lint)
  20. static char rcsid[] OPTIONAL = "$Id: rspf.c,v 1.23 1997/09/07 21:18:28 root Exp root $";
  21. #endif
  22.  
  23. #ifdef RSPF
  24.  
  25. #ifndef    AX25
  26. static struct lq *al_lookup (struct iface *ifp, char *addr, int sort);
  27. #endif /* AX25 */
  28.  
  29. struct rspf_stat Rspf_stat = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  30. struct rspfreasm *Rspfreasmq = NULLRREASM;
  31. struct rspfiface *Rspfifaces = NULLRIFACE;
  32. struct rspfadj *Adjs = NULLADJ;
  33. struct rspfrouter *Rspfrouters = NULLRROUTER;
  34. struct mbuf *Rspfinq = NULLBUF;
  35. struct timer Rspfreasmt, Susptimer;
  36. char *Rrh_message = NULLCHAR;
  37. unsigned short Rspfpingmax = 3;
  38. static int Keeprouter = 0;
  39. static int16 Envelopeid = 0;
  40. static int Nrspfproc = 0;
  41. static unsigned char Rspfsubseq = 0;
  42. static short Rspfseq = -32768L + 1;
  43. static char *findlowroute (uint32 addr, int *low, int add, uint32 * resaddr, int *resbits);
  44. static void makeroutes (void);
  45. static void partialupdate (struct rspfrouter *rr, struct mbuf *bp);
  46. static struct rspfrouter *rr_lookup (uint32 addr);
  47. static void rr_delete (uint32 addr);
  48. static struct rspfiface *rtif_lookup (uint32 addr);
  49. static void rspfcsum (struct mbuf **bpp, uint32 dest);
  50. static void update_in (struct mbuf *bp, uint32 addr);
  51. static void node_in (struct mbuf *bp, uint32 addr, int full);
  52. static void sendonerspf (uint32 addr, uint32 dest);
  53. static void sendtoall (struct mbuf *bp, int nodecnt, struct rspfiface *riface);
  54. static void sendupdate (struct mbuf *bp, int nodecnt, uint32 addr);
  55. static int isnewer (short a, short b);
  56. static void del_reasm (struct rspfreasm *re);
  57. static void reasmtimeout (void *t);
  58. static struct mbuf *rspfreasm (struct mbuf *bp, struct rspfpacketh *rph, uint32 addr);
  59. static struct mbuf *fragmenter (struct mbuf *bp, int nodes, int16 mtu);
  60. static struct mbuf *makeadjupdate (uint32 addr, struct rspfrouter *rr);
  61. static void pushadj (struct mbuf **bpp, uint32 addr, int bits);
  62. static void sendrrh (struct rspfiface *ri);
  63. static void sendrspf (void);
  64. static void goodbadnews (struct rspfadj *adj);
  65. static void add_rspfadj (struct rspfadj *adj);
  66. static void rspfcheck (struct rspfadj *adj);
  67. static void rspfping (int oldstate, void *p, void *v);
  68.  
  69.  
  70.  
  71. /* IP passes its RSPF packets to this function */
  72. void
  73. rspf_input (struct iface *iface, struct ip *ip, struct mbuf *bp, int rxbroadcast OPTIONAL)
  74. {
  75. struct pseudo_header ph;/* Pseudo-header for checksumming */
  76.  
  77.     if (bp == NULLBUF)
  78.         return;
  79.     if (Rspfifaces == NULLRIFACE) {    /* Rspf main loop is not running */
  80.         free_p (bp);
  81.         return;
  82.     }
  83.     ph.length = ip->length - IPLEN - ip->optlen;
  84.     ph.source = ip->source;
  85.     ph.dest = ip->dest;
  86.     ph.protocol = ip->protocol;
  87.     if (cksum (&ph, bp, ph.length) != 0) {
  88.         /* Checksum failed, ignore packet completely */
  89.         free_p (bp);
  90.         ++Rspf_stat.badcsum;
  91.         return;
  92.     }
  93.     bp = pushdown (bp, 1 + sizeof (ip->source) + sizeof (iface));
  94.     *bp->data = RSPFE_PACKET;
  95.     memcpy (bp->data + 1, &ip->source, sizeof (ip->source));
  96.     memcpy (bp->data + 1 + sizeof (ip->source), &iface, sizeof (iface));
  97.     enqueue (&Rspfinq, bp);
  98. }
  99.  
  100.  
  101.  
  102. /* Main loop in RSPF process */
  103. void
  104. rspfmain (int v OPTIONAL, void *v1 OPTIONAL, void *v2 OPTIONAL)
  105. {
  106. union rspf rspf;    /* Internal packet structure */
  107. struct rspfadj *adj = NULLADJ;    /* Adjacency */
  108. struct mbuf *bp, *tbp;
  109. struct rspfiface *riface;
  110. struct iface *iface = NULLIF;
  111. struct route *rp;
  112. uint32 source;        /* Source address */
  113. int cmd;
  114.  
  115.     for ( ; ; ) {
  116.         if (Rspfinq == NULLBUF)
  117.             kwait (&Rspfinq);
  118.         bp = dequeue (&Rspfinq);    /* at least 5 bytes */
  119.         cmd = PULLCHAR (&bp);    /*lint !e506 * get internal event indicator */
  120.         (void) pullup (&bp, (unsigned char *) &source, sizeof (source));
  121.         switch (cmd) {
  122.             case RSPFE_RRH:
  123.                 sendrrh ((struct rspfiface *) source);
  124.                 break;
  125.             case RSPFE_CHECK:
  126.                 rspfcheck ((struct rspfadj *) source);
  127.                 break;
  128.             case RSPFE_UPDATE:
  129.                 sendrspf ();
  130.                 break;
  131.             case RSPFE_ARP:
  132.                 adj = (struct rspfadj *) source;
  133.                 source = adj->addr;    /* fall through */
  134.             case RSPFE_PACKET:
  135.                 (void) pullup (&bp, (unsigned char *) &iface, sizeof (iface));
  136.                 break;
  137.             default:
  138.                 break;
  139.         }
  140.         if (cmd != RSPFE_PACKET && cmd != RSPFE_ARP)
  141.             continue;
  142.         if (cmd == RSPFE_PACKET && ntohrspf (&rspf, &bp) == -1) {
  143.             free_p (bp);
  144.             continue;
  145.         }
  146.         if (iface != NULLIF) {
  147.             for (riface = Rspfifaces; riface != NULLRIFACE; riface =
  148.                  riface->next)
  149.                 if (riface->iface == iface)
  150.                     break;
  151.         } else    /* fails if there is no route or no RSPF interface */
  152.             riface = rtif_lookup (source);
  153.  
  154.         if (riface == NULLRIFACE) {
  155.             free_p (bp);
  156.             if (cmd == RSPFE_PACKET)
  157.                 ++Rspf_stat.norspfiface;
  158.             continue;    /* We do not use RSPF on this interface */
  159.         }
  160.         /* If we dont have an entry in the routing table for this station,
  161.          * or if the entry is less than 32 bits specific or has a higher
  162.          * cost than our new route, and is pointing to the wrong interface,
  163.          * then add a correct, private, route.
  164.          */
  165.         rp = rt_lookup (source);
  166.         if (rp == NULLROUTE || (rp != NULLROUTE && rp->iface !=
  167.                  riface->iface && (rp->bits < 32 || rp->metric >
  168.                            riface->quality))) {
  169.             rp = rt_add (source, 32, 0, iface, riface->quality, 0, 1);
  170.             if (rp != NULLROUTE)
  171.                 set_timer (&rp->timer, MSPTICK);    /* IT9LTA: dummy value, indicates non-manual route */
  172.         }
  173.         if (cmd == RSPFE_ARP) {
  174.             if (adj != NULLADJ) {
  175.                 adj->cost = riface->quality;    /* default cost */
  176.                 add_rspfadj (adj);
  177.                 continue;
  178.             }
  179.         }
  180.         switch (rspf.hdr.type) {    /* packet types */
  181.             case RSPF_RRH:
  182.                 ++Rspf_stat.rrhin;
  183.                 free_p (bp);
  184.                 adj = (struct rspfadj *) callocw (1, sizeof (struct rspfadj));
  185.  
  186.                 adj->addr = rspf.rrh.addr;
  187.                 adj->seq = rspf.rrh.seq;
  188.                 adj->cost = riface->quality;    /* Default cost */
  189.                 adj->state = RSPF_TENTATIVE;
  190.                 if (rspf.rrh.flags & RSPFMODE)
  191.                     adj->tos = DELAY;
  192.                 else
  193.                     adj->tos = RELIABILITY;
  194.                 add_rspfadj (adj);
  195.                 break;
  196.             case RSPF_FULLPKT:
  197.                 ++Rspf_stat.updatein;
  198.                 /* Feed the packet through the reassembly queue */
  199.                 if ((tbp = rspfreasm (bp, &rspf.pkthdr, source)) != NULLBUF)
  200.                     update_in (tbp, source);
  201.                 break;
  202.             default:
  203.                 break;
  204.         }
  205.     }
  206. }
  207.  
  208.  
  209.  
  210. /* This function is called every time an RRH should be broadcasted.
  211.  * An RRH is sent on the interface given by ri or on every RSPF interface.
  212.  * The broadcast address of the interface must be routed onto the same
  213.  * interface (using a static route for instance) otherwise there will be no
  214.  * RRH sent on that interface.
  215.  */
  216. static void
  217. sendrrh (struct rspfiface *ri)        /* interface to use, if specified */
  218. {
  219. struct pseudo_header ph;
  220. struct mbuf *bp, *data = NULLBUF;
  221. struct rspfiface *riface;
  222. struct route *rp;
  223. struct rrh rrh;
  224.  
  225.     for (riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  226.         if (ri != NULLRIFACE && riface != ri)
  227.             continue;
  228.         if ((rp = rt_lookup (riface->iface->broadcast)) != NULLROUTE &&
  229.             rp->iface == riface->iface) {
  230.             rrh.version = RSPF_VERSION;
  231.             rrh.addr = riface->iface->addr;
  232.             ph.length = 0;
  233.             if (Rrh_message != NULLCHAR) {
  234.                 data = ambufw ((int16) strlen (Rrh_message));
  235.                 memcpy (data->data, Rrh_message, strlen (Rrh_message));
  236.                 ph.length = data->cnt = (int16) strlen (Rrh_message);
  237.             }
  238.             ph.length += RRHLEN;
  239.             ph.source = riface->iface->addr;
  240.             ph.dest = riface->iface->broadcast;
  241.             ph.protocol = RSPF_PTCL;
  242.             /* Start the RRH link level packet counter at 1, since adj->seq
  243.              * is 0 only for ARP generated adjacencies. This is also correct
  244.              * since rawsndcnt will increase by one when the RRH is sent.
  245.              */
  246.             rrh.seq = (int16) riface->iface->rawsndcnt + 1;
  247.             /* Default is to use the same mode as the interface */
  248.             if (Rspfownmode == -1)
  249.                 rrh.flags = !(riface->iface->flags & CONNECT_MODE);
  250.             else
  251.                 rrh.flags = !(Rspfownmode & CONNECT_MODE);
  252.  
  253.             bp = htonrrh (&rrh, data, &ph);
  254.             ++Rspf_stat.rrhout;
  255.             (void) ip_send (riface->iface->addr, riface->iface->broadcast, RSPF_PTCL,
  256.                  0, 2, bp, 0, 0, 0);    /* the ttl will be decremented to 1 */
  257.         }
  258.     }
  259. }
  260.  
  261.  
  262.  
  263. /* This function is called whenever an RRH packet has been received or when
  264.  * a new entry is added to the ARP table.
  265.  */
  266. static void
  267. add_rspfadj (struct rspfadj *adj)
  268. {
  269. struct rspfadj *oldadj, *tmp;
  270. struct rspfiface *riface;
  271. struct arp_tab *atp;
  272. struct lq *alp;
  273. int dif, origdif;
  274.  
  275.     if (adj == NULLADJ)
  276.         return;        /* sanity but it happens... */
  277.     if (ismyaddr (adj->addr))    /*is it my RRH (ie, heard my own bcst)? N8RAW */
  278.         return;
  279.     /* Find the previous copy of the adjacency, if there was any */
  280.     /* Insert the new adjacency */
  281.     adj->next = Adjs;
  282.     Adjs = adj;
  283.     for (oldadj = Adjs; oldadj->next != NULLADJ; oldadj = oldadj->next)
  284.         if (oldadj->next->addr == adj->addr) {
  285.             tmp = oldadj->next;
  286.             oldadj->next = oldadj->next->next;
  287.             oldadj = tmp;
  288.             break;
  289.         }
  290.     if (oldadj->addr != adj->addr || oldadj == adj)
  291.         oldadj = NULLADJ;
  292.  
  293.     /* ARP entries give no sequence number, so save the old one */
  294.     if (oldadj != NULLADJ) {
  295.         if (adj->seq == 0)
  296.             adj->seq = oldadj->seq;
  297.         if (adj->tos == 0)
  298.             adj->tos = oldadj->tos;    /* they give no TOS either */
  299.     }
  300.     switch (adj->state) {
  301.         case RSPF_TENTATIVE:
  302.             if (oldadj != NULLADJ) {
  303.                 /* If the adjacency was in OK state, it will remain there.
  304.                  * An RRH or ARP upcall can never generate an OK -> Tentative
  305.                  * transition.
  306.                  */
  307.                 if (oldadj->state == RSPF_OK)
  308.                     adj->state = RSPF_OK;
  309.                 adj->okcnt = oldadj->okcnt;
  310.                 /* If old state was Bad, don't announce this adjacency until
  311.                  * it is known to be OK, to prevent announcing an adjacency
  312.                  * with an state transition loop such as OK -> Suspect -> Bad ->
  313.                  * Tentative -> Suspect -> Bad -> Tentative -> ...
  314.                  */
  315.                 if (oldadj->state == RSPF_BAD) {
  316.                     adj->okcnt = 0;
  317.                     stop_timer (&oldadj->timer);
  318.                     /* Enter Suspect state at once, there is no point in
  319.                      * dwelling as Tentative.
  320.                      */
  321.                     rspfcheck (adj);
  322.                 } else {
  323.                     /* Inherit the old timer */
  324.                     adj->timer.func = rspfevent;
  325.                     adj->timer.arg = (void *) &adj->timer;
  326.                     /* continue where the old timer is stopped */
  327.                     adj->timer.duration = oldadj->timer.duration;
  328.                     stop_timer (&oldadj->timer);
  329.                     /* Set the timer to Suspectimer in the unlikely event that
  330.                      * the timer was stopped and oldadj is not Suspect or Bad.
  331.                      * Suspect state is dealt with further below.
  332.                      */
  333.                     if (dur_timer (&adj->timer) == 0L)
  334.                         set_timer (&adj->timer, dur_timer (&Susptimer));
  335.                     start_detached_timer (&adj->timer);
  336.                     set_timer (&adj->timer, dur_timer (&oldadj->timer));
  337.                 }
  338.                 /* We must now try to figure out from which AX.25 callsign this
  339.                  * packet came. Looking at the ARP table may sometimes help.
  340.                  */
  341.                 if (oldadj->seq != 0 && adj->seq != 0 &&
  342.                     (riface = rtif_lookup (adj->addr)) != NULLRIFACE &&
  343.                     (atp = arp_lookup (ARP_AX25, adj->addr, riface->iface)) != NULLARP &&
  344.                     atp->state == ARP_VALID &&
  345.                     (alp = al_lookup (riface->iface, atp->hw_addr, 0)) != NULLLQ) {
  346.                     /* The wrapping of the modulus is taken into account here */
  347.                     if (oldadj->seq > (MAXINT16 - 100) && adj->seq < 100)
  348.                         origdif = adj->seq + MAXINT16 - oldadj->seq;
  349.                     else
  350.                         origdif = adj->seq - oldadj->seq;
  351.                     if ((alp->currxcnt - adj->heard) > (MAXINT16 - 100)
  352.                         && adj->seq < 100)
  353.                         dif = (int) (origdif + MAXINT16 - (alp->currxcnt - adj->heard));
  354.                     else
  355.                         dif = (int) (origdif - (alp->currxcnt - adj->heard));
  356.                     adj->heard = alp->currxcnt;    /* Update the counter */
  357.                     /* At this point, "origdif" equals the difference in sequence
  358.                      * numbers between the two latest RRH packets, i.e. the
  359.                      * number of AX.25 frames the station has sent during since
  360.                      * the last RRH packet we heard. "dif" equals the number of
  361.                      * AX.25 frames that we actually heard from that station
  362.                      * during the same period.
  363.                      */
  364.                     if (origdif > 0 && dif > 0)
  365.                         /* This algorithm can be improved, see 2.1 spec */
  366.                         adj->cost = uchar(riface->quality * 2 - riface->quality * dif / origdif);
  367.                 }
  368.                 /* Ignore any new RRH's if a pinger process is already running */
  369.                 if (oldadj->state == RSPF_SUSPECT) {
  370.                     if (adj->heard != 0)    /* save new heard count */
  371.                         oldadj->heard = adj->heard;
  372.                     oldadj->next = adj->next;    /* adj is at start of chain */
  373.                     Adjs = oldadj;
  374.                     stop_timer (&adj->timer);
  375.                     free ((char *) adj);
  376.                     return;
  377.                 }
  378.             } else {/* oldadj == NULLADJ */
  379.                 rspfcheck (adj);    /* enter Suspect state */
  380.                 /* A new adjacency may affect the routing table even though no
  381.                  * routing updates have yet been received from it.
  382.                  */
  383.                 makeroutes ();
  384.             }
  385.             break;
  386.         case RSPF_OK:
  387.             if (oldadj != NULLADJ) {
  388.                 adj->okcnt += oldadj->okcnt;    /* Do these before possible */
  389.                 stop_timer (&oldadj->timer);    /* killproc() -- KZ1F */
  390.                 if (oldadj->state == RSPF_SUSPECT) {
  391.                     killproc (oldadj->pinger);
  392.                     --Nrspfproc;    /* Bug fix - N1BEE */
  393.                 }
  394.             } else
  395.                 makeroutes ();    /* routing table may change */
  396.             if (adj->okcnt == 1)    /* A previously unkown route */
  397.                 goodbadnews (adj);    /* ..that is good news */
  398.             break;
  399.         default:
  400.             break;
  401.     }
  402.     if (oldadj) {
  403.         stop_timer (&oldadj->timer);    /* stop timer before free() -- KZ1F */
  404. #ifndef KZ1F
  405.         free ((char *) oldadj);
  406. #endif
  407.     }
  408. }
  409.  
  410.  
  411.  
  412. /* Take appropriate action if an adjacency is Bad or Tentative */
  413. static void
  414. rspfcheck (struct rspfadj *adj)
  415. {
  416. struct rspfadj *prev;
  417.  
  418.     for (prev = Adjs; prev != NULLADJ; prev = prev->next)
  419.         if (prev->next == adj)
  420.             break;
  421.     switch (adj->state) {
  422.         case RSPF_OK:
  423.             adj->state = RSPF_TENTATIVE;    /* note fall-thru */
  424.         case RSPF_TENTATIVE:
  425.             if (Nrspfproc < RSPF_PROCMAX) {
  426.                 Nrspfproc++;
  427.                 adj->pinger = newproc ("RSPF ping", 1024, rspfping,
  428.                         (int) adj->state, adj, NULL, 0);
  429.                 adj->state = RSPF_SUSPECT;    /* The adjacency is now Suspect */
  430.             } else {/* Try later */
  431.                 set_timer (&adj->timer, dur_timer (&Susptimer));
  432.                 start_detached_timer (&adj->timer);
  433.             }
  434.             break;
  435.         case RSPF_BAD:
  436.             rr_delete (adj->addr);
  437.             adj->cost = 255;
  438.             if (adj->okcnt != 0)
  439.                 goodbadnews (adj);    /* This is bad news... */
  440.             if (prev != NULLADJ)
  441.                 prev->next = adj->next;    /* Unlink */
  442.             else
  443.                 Adjs = adj->next;
  444.             stop_timer (&adj->timer);    /* just in case */
  445.             free ((char *) adj);    /* delete the adjacency */
  446.             makeroutes ();    /* update the routing table */
  447.             break;
  448.         default:
  449.             break;
  450.     }
  451. }
  452.  
  453.  
  454.  
  455. /* Send a ping to a suspect or tentative adjacency */
  456. static void
  457. rspfping (int oldstate, void *p, void *v OPTIONAL)
  458. {
  459. int s, fromlen, pcnt;
  460. struct icmp icmp;
  461. struct rspfadj *adj;
  462. struct sockaddr_in from;
  463. struct mbuf *bp;
  464.  
  465.     (void) kpause (((ptol (p) & 7) + 1) * 1000L);    /* Pause for 1 to 8 seconds */
  466.     adj = (struct rspfadj *) p;
  467.     adj->timer.func = rspfevent;    /* Fill in timer values */
  468.     adj->timer.arg = (void *) &adj->timer;
  469.     set_timer (&adj->timer, dur_timer (&Susptimer));
  470.     if ((s = socket (AF_INET, SOCK_RAW, ICMP_PTCL)) == -1) {
  471.         --Nrspfproc;
  472.         adj->state = (char) oldstate;
  473.         start_detached_timer (&adj->timer);
  474.         return;
  475.     }
  476.     fromlen = sizeof (from);
  477.     for (pcnt = 0; pcnt < Rspfpingmax; ++pcnt) {
  478.         pingem (s, adj->addr, 0, (int16) s, 0);
  479.         /* Now collect the reply */
  480.         kalarm (60 * 1000L);    /* Let each ping timeout after 60 seconds */
  481.         for ( ; ; ) {
  482.             if (recv_mbuf (s, &bp, 0, (char *) &from, &fromlen) == -1) {
  483.                 if (errno == EALARM) {    /* We timed out */
  484.                     break;
  485.                 }
  486.                 kalarm (0);
  487.                 adj->state = (char) oldstate;
  488.                 close_s (s);
  489.                 --Nrspfproc;
  490.                 start_detached_timer (&adj->timer);
  491.                 return;
  492.             }
  493.             (void) ntohicmp (&icmp, &bp);
  494.             free_p (bp);
  495.             if (icmp.type != ICMP_ECHO_REPLY || from.sin_addr.s_addr !=
  496.             (unsigned long) adj->addr || icmp.args.echo.id != s)
  497.                 /* Ignore other people's responses */
  498.                 continue;
  499.             kalarm (0);
  500.             if (++adj->okcnt == 1)
  501.                 goodbadnews (adj);    /* Good news */
  502.             close_s (s);
  503.             --Nrspfproc;
  504.             start_detached_timer (&adj->timer);
  505.             adj->state = RSPF_OK;    /* Finally change state */
  506.             return;
  507.         }
  508.     }
  509.     /* we give up, mark the adjacency as bad */
  510.     adj->state = RSPF_BAD;
  511.     close_s (s);
  512.     --Nrspfproc;
  513.     start_detached_timer (&adj->timer);
  514. }
  515.  
  516.  
  517.  
  518. /* ARP upcalls come in two flavors: When an ARP Reply has been received, we
  519.  * know for certain that bidirectional communication is possible with the
  520.  * particular station. But when an ARP Request is received, or if an ARP
  521.  * entry is added manually, it has yet to be determined if the link is
  522.  * bidirectional so iface is NULLIF in those cases.
  523.  */
  524. void
  525. rspfarpupcall (
  526. uint32 addr,            /* Address being added to ARP table */
  527. int16 hardware,            /* Hardware type */
  528. struct iface *iface        /* Interface used, if known */
  529. ) {
  530. struct rspfadj *adj;
  531. struct mbuf *bp;
  532. struct rspfiface *riface;
  533.  
  534.     if ((riface = rtif_lookup (addr)) == NULLRIFACE)
  535.         return;        /* Not a route to an RSPF interface */
  536.     /* Proceed only if the ARP entry is for a hardware type that is relevant
  537.      * for the interface onto which IP datagrams are routed.
  538.      */
  539.     switch (hardware) {
  540.         case ARP_NETROM:
  541.             if (riface->iface->type != CL_NETROM)
  542.                 return;
  543.             break;
  544.         case ARP_AX25:
  545.             if (riface->iface->type != CL_AX25)
  546.                 return;
  547.             break;
  548.         case ARP_ETHER:
  549.             if (riface->iface->type != CL_ETHERNET)
  550.                 return;
  551.             break;
  552.         case NHWTYPES:    /* "Any interface type is ok" type entry */
  553.         default:
  554.             return;
  555.     }
  556.     if ((adj = (struct rspfadj *) callocw (1, sizeof (struct rspfadj))) == NULLADJ)
  557.                 return;
  558.  
  559.     adj->addr = addr;
  560.     if (iface == NULLIF)    /* A manual ARP entry or Request, may be no-good */
  561.         adj->state = RSPF_TENTATIVE;
  562.     else {
  563.         adj->state = RSPF_OK;
  564.         adj->okcnt++;
  565.         adj->timer.func = rspfevent;    /* Fill in timer values */
  566.         adj->timer.arg = (void *) &adj->timer;
  567.         set_timer (&adj->timer, dur_timer (&Susptimer));
  568.         start_detached_timer (&adj->timer);
  569.     }
  570.     if ((bp = alloc_mbuf (1 + sizeof (int32) + sizeof (iface))) == NULLBUF) {
  571.         stop_timer (&adj->timer);
  572.         free ((char *) adj);
  573.         return;
  574.     }
  575.     *bp->data = RSPFE_ARP;
  576.     memcpy (bp->data + 1, (char *) &adj, sizeof (adj));
  577.     memcpy (bp->data + 1 + sizeof (adj), (char *) &iface, sizeof (iface));
  578.     bp->cnt = bp->size;
  579.     enqueue (&Rspfinq, bp);
  580. }
  581.  
  582.  
  583.  
  584. /* Called by "route add" command. */
  585. void
  586. rspfrouteupcall (
  587. uint32 addr,            /* Address added to routing table */
  588. unsigned bits,            /* Significant bits in address */
  589. uint32 gateway            /* Address of gateway station */
  590. ) {
  591.     /* We are only interested in 32 bit specific routes that use a
  592.      * gateway. Direct routes will be discovered anyway.
  593.      */
  594.     if (bits != 32 || gateway == 0 || gateway == addr)
  595.         return;
  596.     if (rtif_lookup (addr) == NULLRIFACE)    /* not routed onto RSPF interface */
  597.         return;
  598.     rspfarpupcall (addr, NHWTYPES, NULLIF);    /* proceed as an "arp add" upcall */
  599. }
  600.  
  601.  
  602.  
  603. /* When the suspect timer expires, we scan through the routing table for all
  604.  * manual 32 bit specific routes through a gateway that are not an adjacency,
  605.  * and calls rspfrouteupcall(). A similar thing is done for all manual ARP
  606.  * entries. This will make sure that a station that was not reachable when
  607.  * the "route add" or "arp add" command was executed will eventually be
  608.  * discovered if it joins the network.
  609.  */
  610. void
  611. rspfsuspect (void *t OPTIONAL)
  612. {
  613. struct rspfadj *adj;
  614. struct route *rp;
  615. struct arp_tab *ap;
  616. int i;
  617.  
  618.     start_detached_timer (&Susptimer);    /* restart the timer */
  619.     for (i = 0; i < HASHMOD; i++)    /* Check the routing table */
  620.         for (rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next) {
  621.             if ((rp->flags & RTPRIVATE) || dur_timer (&rp->timer) != 0)
  622.                 continue;    /* not this route */
  623.             for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  624.                 if (adj->addr == rp->target)
  625.                     break;
  626.             if (adj == NULLADJ)    /* it is not already an adjacency */
  627.                 rspfrouteupcall (rp->target, 32, rp->gateway);
  628.         }
  629.     for (i = 0; i < HASHMOD; ++i)    /* scan the ARP table */
  630.         for (ap = Arp_tab[i]; ap != NULLARP; ap = ap->next) {
  631.             if (dur_timer (&ap->timer))    /* not a manual entry */
  632.                 continue;
  633.             for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  634.                 if (adj->addr == ap->ip_addr)
  635.                     break;
  636.             if (adj == NULLADJ)    /* not already an adjacency */
  637.                 rspfarpupcall (ap->ip_addr, ap->hardware, NULLIF);
  638.         }
  639. }
  640.  
  641.  
  642.  
  643. /* This non-layered function peeks at the routing table to figure out to which
  644.  * interface datagrams for addr will be routed. Then it returns the matching
  645.  * rspfiface structure.
  646.  */
  647. static
  648. struct rspfiface *
  649. rtif_lookup (uint32 addr)
  650. {
  651. struct rspfiface *riface;
  652. struct route *rp;
  653.  
  654.     if ((rp = rt_lookup (addr)) == NULLROUTE)
  655.         return NULLRIFACE;
  656.     riface = Rspfifaces;
  657.     while (riface != NULLRIFACE) {
  658.         if (riface->iface == rp->iface)
  659.             return riface;
  660.         riface = riface->next;
  661.     }
  662.     return NULLRIFACE;
  663. }
  664.  
  665.  
  666.  
  667. /* Send good or bad news partial routing updates. A cost of 255 should be
  668.  * interpreted as bad news by the remote station.
  669.  */
  670. static void
  671. goodbadnews (struct rspfadj *adj)
  672. {
  673. struct rspfnodeh nodeh;
  674. struct rspflinkh linkh;
  675. struct rspfiface *riface;
  676. struct rspfrouter *rr;
  677. struct mbuf *bp, *tbp, *wbp;
  678. int nodecnt = 1;
  679.  
  680.     if ((riface = rtif_lookup (adj->addr)) == NULLRIFACE)
  681.         return;
  682.     bp = ambufw (5);
  683.     bp->cnt = bp->size;
  684.     *bp->data = 32;        /* the number of significant bits in the address */
  685.     (void) put32 (bp->data + 1, adj->addr);
  686.     linkh.horizon = riface->horizon;
  687.     linkh.erp = riface->erp;
  688.     linkh.cost = adj->cost;
  689.     linkh.adjn = 1;
  690.     tbp = htonrspflink (&linkh, bp);
  691.     nodeh.seq = Rspfseq;
  692.     nodeh.subseq = ++Rspfsubseq;
  693.     nodeh.links = 1;
  694.     for (riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  695.         if (dup_p (&wbp, tbp, 0, len_p (tbp)) != len_p (tbp)) {
  696.             free_p (wbp);
  697.             continue;
  698.         }
  699.         nodeh.addr = riface->iface->addr;
  700.         bp = htonrspfnode (&nodeh, wbp);
  701.         sendtoall (bp, 1, riface);
  702.     }
  703.     free_p (tbp);
  704.     /* If this is a new adjacency, then send it a routing update immediately */
  705.     if (adj->cost == 255 || adj->okcnt != 1)
  706.         return;
  707.     /* When two RSPF stations learn about each others existence, one of
  708.      * them will usually have received an RRH from the other. The one that
  709.      * received the RRH will send the peer a routing update immediately.
  710.      * So in the code below, if no RRH has been received (seq is 0) and no
  711.      * routing update has yet been received, we should expect to receive a
  712.      * routing update shortly if the adjacency is running RSPF.
  713.      * This could fail though if two RSPF stations learn about each other
  714.      * solely through ARP upcalls and no RRH's or Updates were exchanged
  715.      * prior to or during the establishment of the adjacency.
  716.      */
  717.     if (adj->seq == 0 && rr_lookup (adj->addr) == NULLRROUTER) {
  718.         if (adj->state != RSPF_SUSPECT)    /* running in RSPF process, give up */
  719.             return;
  720.         kalarm (15 * 1000);    /* wait for an Update */
  721.         if (kwait (adj) == EALARM)
  722.             return;    /* still no sign of RSPF activity from the adjacency */
  723.         kalarm (0);
  724.     }
  725.     ++adj->okcnt;        /* we don't want to get here again */
  726.     if ((bp = makeownupdate (adj->addr, 1)) == NULLBUF)
  727.         return;
  728.     for (rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  729.         if ((tbp = makeadjupdate (get32 ((char *) rr->data->data), rr)) != NULLBUF) {
  730.             append (&bp, tbp);
  731.             nodecnt++;
  732.         }
  733.     sendupdate (bp, nodecnt, adj->addr);
  734. }
  735.  
  736.  
  737.  
  738. /* This function is called whenever it is time to send a new RSPF update */
  739. static void
  740. sendrspf (void)
  741. {
  742. struct rspfrouter *rr;
  743. struct mbuf *bp, *wbp, *tmp = NULLBUF;
  744. struct rspfiface *riface;
  745. struct rspfadj *adj;
  746. int nodecnt, incr = 1;
  747.  
  748.     for (nodecnt = 1, rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  749.         if (!rr->sent)    /* don't send stale data */
  750.             if ((bp = makeadjupdate (get32 ((char *) rr->data->data), rr)) != NULLBUF) {
  751.                 append (&tmp, bp);
  752.                 nodecnt++;
  753.             }
  754.     for (riface = Rspfifaces; riface != NULLRIFACE; riface = riface->next) {
  755.         /* Find an address that is routed onto this interface */
  756.         for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  757.             if (rtif_lookup (adj->addr) == riface)
  758.                 break;
  759.         if (adj == NULLADJ)    /* no adjacency on that interface? */
  760.             continue;
  761.         if (dup_p (&wbp, tmp, 0, len_p (tmp)) != len_p (tmp)) {
  762.             free_p (wbp);
  763.             continue;
  764.         }
  765.         if ((bp = makeownupdate (adj->addr, incr)) != NULLBUF) {
  766.             incr = 0;    /* sequence number is incremented only once */
  767.             append (&bp, wbp);
  768.         } else
  769.             break;
  770.         sendtoall (bp, nodecnt, riface);
  771.     }
  772.     free_p (tmp);
  773.     for (rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  774.         if (!rr->sent)    /* Mark router data as propagated */
  775.             ++rr->sent;
  776. }
  777.  
  778.  
  779.  
  780. /* This function is used to answer "poll" messages */
  781. static void
  782. sendonerspf (
  783. uint32 addr,            /* address of station whose routing update we will make */
  784. uint32 dest            /* address of station to send the update to */
  785. ) {
  786. struct mbuf *bp;
  787.  
  788.     if (ismyaddr (addr)) {
  789.         if ((bp = makeownupdate (dest, 0)) == NULLBUF)
  790.             return;
  791.         sendupdate (bp, 1, dest);
  792.         return;
  793.     }
  794.     if ((bp = makeadjupdate (addr, NULLRROUTER)) == NULLBUF)
  795.         return;
  796.     sendupdate (bp, 1, dest);
  797. }
  798.  
  799.  
  800.  
  801. /* send an update to all adjacencies on an RSPF interface */
  802. static void
  803. sendtoall (
  804. struct mbuf *bp,
  805. int nodecnt,            /* number of reporting nodes in update */
  806. struct rspfiface *riface    /* interface to sent to */
  807. ) {
  808. struct rspfadj *adj;
  809. struct mbuf *wbp;
  810. int broad;
  811.  
  812.     for (broad = 0, adj = Adjs; adj != NULLADJ; adj = adj->next)
  813.         /* If adj->seq is 0 we have never received an RRH from the
  814.          * adjacency, and if there is no stored routing update, then
  815.          * it is not known if the adjacency understands RSPF.
  816.          */
  817.         if ((adj->seq != 0 || rr_lookup (adj->addr) != NULLRROUTER) &&
  818.             riface == rtif_lookup (adj->addr)) {
  819.             if ((adj->tos & RELIABILITY) && !(adj->tos & DELAY)) {
  820.                 if (dup_p (&wbp, bp, 0, len_p (bp)) != len_p (bp)) {
  821.                     free_p (wbp);
  822.                     continue;
  823.                 }
  824.                 sendupdate (wbp, nodecnt, adj->addr);    /* private copy */
  825.             } else
  826.                 ++broad;    /* send to broadcast IP address instead */
  827.         }
  828.     if (broad != 0)
  829.         if (dup_p (&wbp, bp, 0, len_p (bp)) != len_p (bp))
  830.             free_p (wbp);
  831.         else
  832.             sendupdate (wbp, nodecnt, riface->iface->broadcast);
  833.     free_p (bp);
  834. }
  835.  
  836.  
  837.  
  838. /* This function sends a routing update to the adjacencies that we have
  839.  * recevied RRH's from.
  840.  */
  841. static void
  842. sendupdate (
  843. struct mbuf *bp,        /* Full packet, except for the packet header */
  844. int nodecnt,            /* Number of reporting nodes in the packet */
  845. uint32 addr            /* Station to send update to */
  846. ) {
  847. struct rspfadj *adj;
  848. struct mbuf *tmp;
  849. int tos = 0;
  850.  
  851.     /* See if we are sending to a known adjacency, in use its TOS in
  852.      * that case.
  853.      */
  854.     for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  855.         if (adj->addr == addr) {
  856.             tos = adj->tos;
  857.             break;
  858.         }
  859.     if ((tmp = fragmenter (bp, nodecnt, ip_mtu (addr) - IPLEN)) == NULLBUF)
  860.         return;
  861.     while ((bp = dequeue (&tmp)) != NULLBUF) {
  862.         rspfcsum (&bp, addr);    /* Calculate the checksum */
  863.         ++Rspf_stat.updateout;
  864.         (void) ip_send (INADDR_ANY, addr, RSPF_PTCL, (char) (INET_CTL | tos), 2, bp, 0, 0, 0);
  865.     }
  866.     return;
  867. }
  868.  
  869.  
  870.  
  871. /* Fragment a large mbuf if necessary into packets of maximum mtu bytes.
  872.  * Each packet is prepended a RSPF routing update header, without the checksum.
  873.  */
  874. static struct mbuf *
  875. fragmenter (
  876. struct mbuf *bp,        /* packet to send, without packet header */
  877. int nodes,            /* The number of reporting nodes in the routing update */
  878. int16 mtu            /* The maximum transmission unit */
  879. ) {
  880. struct rspfnodeh nodeh;
  881. struct rspflinkh linkh;
  882. struct rspfpacketh pkth;
  883. struct mbuf *tbp, *tmp, *bpq = NULLBUF;
  884. int n, nodecnt, linkcnt, adjcnt, nodemax, thesync;
  885. char *cp = NULLCHAR, fragn = 1;
  886.  
  887.     if (mtu < RSPFPKTLEN + RSPFNODELEN || bp == NULLBUF) {
  888.         free_p (bp);
  889.         return NULLBUF;
  890.     }
  891.     ++Envelopeid;
  892.     nodemax = nodes;    /* total number of nodes in envelope */
  893.     nodecnt = nodes;    /* nodes left to packetize */
  894.     linkcnt = adjcnt = 0;
  895.  
  896.     while (len_p (bp) != 0) {
  897.         int16 tmpint;
  898.         tmpint = len_p (bp) + RSPFPKTLEN;
  899.         n = min (mtu, tmpint);    /* length of this packet */
  900.         n -= RSPFPKTLEN;
  901.         tbp = NULLBUF;
  902.         thesync = 0;
  903.         if (adjcnt) {
  904.             tbp = ambufw ((int16) min (adjcnt * 5, n / 5 * 5));
  905.             tbp->cnt = tbp->size;
  906.             cp = (char *) tbp->data;
  907.         }
  908.         while (n > 0) {
  909.             while (adjcnt) {
  910.                 if ((n -= 5) < 0)
  911.                     break;
  912.                 (void) pullup (&bp, (unsigned char *) cp, 5);
  913.                 if (cp)
  914.                     cp += 5;
  915.                 adjcnt--;
  916.             }
  917.             if (linkcnt && n > 0) {
  918.                 if ((n -= RSPFLINKLEN) < 0)
  919.                     break;
  920.                 (void) ntohrspflink (&linkh, &bp);
  921.                 adjcnt = linkh.adjn;
  922.                 tmp = htonrspflink (&linkh, NULLBUF);
  923.                 append (&tbp, tmp);
  924.                 tmp = ambufw ((int16) min (5 * adjcnt, n / 5 * 5));
  925.                 tmp->cnt = tmp->size;
  926.                 cp = (char *) tmp->data;
  927.                 append (&tbp, tmp);
  928.                 linkcnt--;
  929.                 continue;
  930.             }
  931.             if (nodecnt && linkcnt == 0 && n > 0) {
  932.                 if ((n -= RSPFNODELEN) < 0)
  933.                     break;
  934.                 if (nodecnt == nodes)    /* Set the sync octet */
  935.                     thesync = len_p (tbp) + 4;
  936.                 (void) ntohrspfnode (&nodeh, &bp);
  937.                 linkcnt = nodeh.links;
  938.                 tmp = htonrspfnode (&nodeh, NULLBUF);
  939.                 append (&tbp, tmp);
  940.                 nodecnt--;
  941.             }
  942.         }
  943.         pkth.version = RSPF_VERSION;    /* The version number */
  944.         pkth.type = RSPF_FULLPKT;    /* The packet type */
  945.         pkth.fragn = uchar(fragn++);    /* The fragment number */
  946.         pkth.fragtot = 0;    /* The total number of fragments */
  947.         pkth.csum = 0;    /* The checksum */
  948.         pkth.sync = uchar(thesync < 256 ? thesync : 0);    /* The sync octet */
  949.         pkth.nodes = uchar(nodemax);    /* The number of nodes in envelope */
  950.         pkth.envid = Envelopeid;    /* The envelope-ID */
  951.         tmp = htonrspf (&pkth, tbp);    /* add packet header */
  952.         enqueue (&bpq, tmp);    /* add packet to chain */
  953.         nodes = nodecnt;/* number of nodes left */
  954.     }
  955.     free_p (bp);
  956.     for (tbp = bpq; tbp != NULLBUF; tbp = tbp->anext)
  957.         *(tbp->data + 3) = uchar(len_q (bpq));    /* Set the fragment total counter */
  958.     return bpq;
  959. }
  960.  
  961.  
  962.  
  963. /* Calculate the checksum on an RSPF routing update packet */
  964. static void
  965. rspfcsum (struct mbuf **bpp, uint32 dest)
  966. {
  967. struct pseudo_header ph;
  968. int16 thechecksum;
  969.  
  970.     ph.length = len_p (*bpp);
  971.     ph.source = locaddr (dest);
  972.     ph.dest = dest;
  973.     ph.protocol = RSPF_PTCL;
  974.     if ((thechecksum = cksum (&ph, *bpp, ph.length)) == 0)
  975.         /* was thechecksum = 0xffffffff - odd, since it is a int16! */
  976.         thechecksum = 0xffff;
  977.     /* This assumes that the checksum really is at this position */
  978.     (void) put16 ((*bpp)->data + 4, thechecksum);
  979. }
  980.  
  981.  
  982.  
  983. /* This function creates our own routing update and returns it in an mbuf */
  984. struct mbuf *
  985. makeownupdate (
  986. uint32 dest,            /* Address of a station that will get this update */
  987. int new                /* True if the sequence number should be incremented */
  988. ) {
  989. struct rspfadj *adj;
  990. struct rspflinkh linkh;
  991. struct rspfnodeh nodeh;
  992. struct rspfiface *riface, rifdefault;
  993. struct mbuf *bp = NULLBUF, *tbp, *tmp;
  994. struct route *rp;
  995. int i, adjcnt, lnkcnt, bits;
  996. int32 prev, low, cur;
  997.  
  998.     /* Set default values to apply to non-RSPF interfaces */
  999.     rifdefault.horizon = 32;
  1000.     rifdefault.erp = 0;
  1001.     rifdefault.quality = 0;
  1002.     /* Our adjacencies has to be sorted into groups of the same horizon,
  1003.      * ERP factor and cost. This is done by combining these numbers into a
  1004.      * single one, modulo 256 and take the lowest number first.
  1005.      */
  1006.     low = 0;
  1007.     lnkcnt = 0;
  1008.     for ( ; ; ) {
  1009.         prev = low;
  1010.         low = 255 * 65536L + 255 * 256 + 255;
  1011.         for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  1012.             /* Include all adjacecies that have been or are in OK state
  1013.              * in the update. Bad adjacencies are also included to give
  1014.              * them a chance to recover. Hopelessly Bad adjacencies are
  1015.              * eventually deleted elsewhere.
  1016.              */
  1017.             if (adj->okcnt != 0 && (riface = rtif_lookup (adj->addr)) !=
  1018.                 NULLRIFACE) {
  1019.                 cur = riface->horizon * 65536L + riface->erp * 256 + adj->cost;
  1020.                 if (cur > prev && cur < low)
  1021.                     low = cur;
  1022.             }
  1023.         /* Add any manual public, 1-31 bit specific routes.
  1024.          * Use the route metric only if it is greater than the default
  1025.          * quality to lessen a possible "wormhole" effect.
  1026.          */
  1027.         for (bits = 1; bits <= 31; bits++)
  1028.             for (i = 0; i < HASHMOD; i++)
  1029.                 for (rp = Routes[bits - 1][i]; rp != NULLROUTE; rp = rp->next)
  1030.                     if (!(rp->flags & RTPRIVATE) && !dur_timer (&rp->timer)) {
  1031.                         if ((riface = rtif_lookup (rp->target)) == NULLRIFACE)
  1032.                             riface = &rifdefault;
  1033.                         cur = riface->horizon * 65536L + riface->erp * 256 +
  1034.                             (rp->metric > riface->quality ? rp->metric :
  1035.                              riface->quality);
  1036.                         if (cur > prev && cur < low)
  1037.                             low = cur;
  1038.                     }
  1039.         /* Add any 32 bit routes on interfaces not using RSPF */
  1040.         for (i = 0; i < HASHMOD; i++)
  1041.             for (rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
  1042.                 if (!(rp->flags & RTPRIVATE) && rtif_lookup (rp->target)
  1043.                     == NULLRIFACE) {
  1044.                     cur = rifdefault.horizon * 65536L + rifdefault.erp * 256 +
  1045.                         (rp->metric > rifdefault.quality ? rp->metric :
  1046.                          rifdefault.quality);
  1047.                     if (cur > prev && cur < low)
  1048.                         low = cur;
  1049.                 }
  1050.         /* Add the default route */
  1051.         if ((rp = rt_blookup (0, 0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
  1052.             !dur_timer (&rp->timer)) {
  1053.             if ((riface = rtif_lookup (0)) == NULLRIFACE)
  1054.                 riface = &rifdefault;
  1055.             cur = riface->horizon * 65536L + riface->erp * 256 +
  1056.                 (rp->metric > riface->quality ? rp->metric : riface->quality);
  1057.             if (cur > prev && cur < low)
  1058.                 low = cur;
  1059.         }
  1060.         if (low == 255 * 65536L + 255 * 256 + 255)    /* All done */
  1061.             break;
  1062.         /* now start adding the routes */
  1063.         adjcnt = 0;
  1064.         tbp = NULLBUF;
  1065.         for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  1066.             if (adj->okcnt != 0 && (riface = rtif_lookup (adj->addr)) !=
  1067.                 NULLRIFACE)
  1068.                 if (riface->horizon * 65536L + riface->erp * 256 + adj->cost == low) {
  1069.                     pushadj (&tbp, adj->addr, 32);
  1070.                     adjcnt++;
  1071.                 }
  1072.         for (bits = 1; bits <= 31; bits++)
  1073.             for (i = 0; i < HASHMOD; i++)
  1074.                 for (rp = Routes[bits - 1][i]; rp != NULLROUTE; rp = rp->next)
  1075.                     if (!(rp->flags & RTPRIVATE) && !dur_timer (&rp->timer)) {
  1076.                         if ((riface = rtif_lookup (rp->target)) == NULLRIFACE)
  1077.                             riface = &rifdefault;
  1078.                         /* Manually entered local routes only */
  1079.                         if (riface->horizon * 65536L + riface->erp * 256 +
  1080.                             (rp->metric > riface->quality ? rp->metric :
  1081.                           riface->quality) == low) {
  1082.                             pushadj (&tbp, rp->target, bits);
  1083.                             adjcnt++;
  1084.                         }
  1085.                     }
  1086.         for (i = 0; i < HASHMOD; i++)    /* 32 bit specific routes */
  1087.             for (rp = Routes[31][i]; rp != NULLROUTE; rp = rp->next)
  1088.                 if (!(rp->flags & RTPRIVATE) && rtif_lookup (rp->target)
  1089.                     == NULLRIFACE)
  1090.                     if (rifdefault.horizon * 65536L + rifdefault.erp * 256 +
  1091.                         (rp->metric > rifdefault.quality ? rp->metric :
  1092.                          rifdefault.quality) == low) {
  1093.                         pushadj (&tbp, rp->target, bits);
  1094.                         adjcnt++;
  1095.                     }
  1096.         /* Add the default route */
  1097.         if ((rp = rt_blookup (0, 0)) != NULLROUTE && !(rp->flags & RTPRIVATE) &&
  1098.             !dur_timer (&rp->timer)) {
  1099.             if ((riface = rtif_lookup (0)) == NULLRIFACE)
  1100.                 riface = &rifdefault;
  1101.             if (riface->horizon * 65536L + riface->erp * 256 + (rp->metric >
  1102.                                         riface->quality ? rp->metric : riface->quality) == low) {
  1103.                 pushadj (&tbp, 0, 0);
  1104.                 adjcnt++;
  1105.             }
  1106.         }
  1107.         if (adjcnt != 0) {
  1108.             /* Prepend the link header */
  1109.             linkh.horizon = ((low >> 16) & 255);    /*lint !e704 * Horizon value */
  1110.             linkh.erp = ((low >> 8) & 255);        /*lint !e704 * ERP factor */
  1111.             linkh.cost = (low & 255);        /* Link cost */
  1112.             linkh.adjn = uchar(adjcnt);        /* Number of adjacencies */
  1113.             tmp = htonrspflink (&linkh, tbp);
  1114.             append (&bp, tmp);
  1115.             lnkcnt++;
  1116.         }
  1117.     }
  1118.     /* Prepend the node header */
  1119.     if (lnkcnt != 0) {
  1120.         /* Set our address to the IP address used on the destinations
  1121.          * interface.
  1122.          */
  1123.         if (dest == INADDR_ANY || (riface = rtif_lookup (dest)) == NULLRIFACE)
  1124.             nodeh.addr = Ip_addr;
  1125.         else
  1126.             nodeh.addr = riface->iface->addr;
  1127.         if (new) {    /* increase sequence number, clear subseq. number */
  1128.             if (Rspfseq == 32768L - 2 || Rspfseq == -32768L + 1)
  1129.                 Rspfseq = 0;    /* wrap around */
  1130.             else
  1131.                 ++Rspfseq;
  1132.             Rspfsubseq = 0;
  1133.         }
  1134.         nodeh.seq = Rspfseq;
  1135.         nodeh.subseq = 0;
  1136.         nodeh.links = uchar(lnkcnt);
  1137.         return htonrspfnode (&nodeh, bp);
  1138.     } else {
  1139.         free_p (bp);
  1140.         return NULLBUF;
  1141.     }
  1142. }
  1143.  
  1144.  
  1145.  
  1146. /* Prepends an adjacency to bpp. Allocates bpp in large chunk for efficency */
  1147. static void
  1148. pushadj (struct mbuf **bpp, uint32 addr, int bits)
  1149. {
  1150.     if (bpp == NULLBUFP)
  1151.         return;
  1152.     if (*bpp == NULLBUF) {
  1153.         *bpp = ambufw (60);    /* good for 12 adjacencies */
  1154.         (*bpp)->data += 55;
  1155.         (*bpp)->cnt = 5;
  1156.     } else
  1157.         *bpp = pushdown (*bpp, 5);
  1158.     *(*bpp)->data = uchar(bits);
  1159.     (void) put32 ((*bpp)->data + 1, addr);
  1160. }
  1161.  
  1162.  
  1163.  
  1164. /* This function returns the latest routing update in network fromat from
  1165.  * the adjacency denoted by addr.
  1166.  */
  1167. static struct mbuf *
  1168. makeadjupdate (
  1169. uint32 addr,
  1170. struct rspfrouter *rr        /* pointer to stored routing entry, if known */
  1171. ) {
  1172. struct mbuf *tmp, *tmp2, *tmp3, *bp = NULLBUF;
  1173. struct rspfnodeh nodeh;
  1174. struct rspflinkh linkh;
  1175. int linkcnt = 0;
  1176.  
  1177.     if (rr == NULLRROUTER && (rr = rr_lookup (addr)) == NULLRROUTER)
  1178.         return NULLBUF;
  1179.     if (dup_p (&tmp, rr->data, 0, len_p (rr->data)) != len_p (rr->data)) {
  1180.         free_p (tmp);
  1181.         return NULLBUF;
  1182.     }
  1183.     (void) ntohrspfnode (&nodeh, &tmp);    /* Get the node header */
  1184.     while (nodeh.links--) {
  1185.         (void) ntohrspflink (&linkh, &tmp);
  1186.         /* Decrement and check the horizon value */
  1187.         if (--linkh.horizon > 0) {
  1188.             /* Duplicate the adjacencies */
  1189.             if (dup_p (&tmp2, tmp, 0, 5 * linkh.adjn) != 5 * linkh.adjn) {
  1190.                 free_p (tmp);
  1191.                 free_p (tmp2);
  1192.                 free_p (bp);
  1193.                 return NULLBUF;
  1194.             }
  1195.             /* Prepend the link header */
  1196.             tmp3 = htonrspflink (&linkh, tmp2);
  1197.             append (&bp, tmp3);
  1198.             linkcnt++;
  1199.         }
  1200.         (void) pullup (&tmp, (unsigned char *)0, 5 * linkh.adjn);    /* Skip the adjacencies */
  1201.     }
  1202.     free_p (tmp);
  1203.     if (linkcnt == 0) {    /* No links at all? */
  1204.         free_p (bp);
  1205.         return NULLBUF;
  1206.     }
  1207.     nodeh.subseq = uchar(rr->subseq);
  1208.     nodeh.links = uchar(linkcnt);
  1209.     /* Prepend the node header */
  1210.     return htonrspfnode (&nodeh, bp);
  1211. }
  1212.  
  1213.  
  1214.  
  1215. /* Returns 1 if sequence number a is newer than b. Sequence numbers start
  1216.  * at -32768 + 1 and then continues with 0 and the positive integer numbers
  1217.  * until reaching 32768 - 2 after which they continue with 0.
  1218.  * Algorithm taken from RFC-1131 but fixed bug when a or b is 0.
  1219.  */
  1220. static int
  1221. isnewer (short a, short b)
  1222. {
  1223.     if ((b < 0 && a > b) ||
  1224.         (a >= 0 && b >= 0 && /* bug corrected here */
  1225.         (((32768L - 1) / 2 > (a - b) && (a - b) > 0) ||
  1226.         (a - b) < -(32768L - 1) / 2)))
  1227.         return 1;
  1228.     return 0;
  1229. }
  1230.  
  1231.  
  1232.  
  1233. /* Reassemble possibly fragmented packets into a single large one */
  1234. static struct mbuf *
  1235. rspfreasm (
  1236. struct mbuf *bp,        /* Routing update packet without packet header */
  1237. struct rspfpacketh *rph,    /* Packet header */
  1238. uint32 addr            /* Address of station we got the packet from */
  1239. ) {
  1240. union rspf rspf;
  1241. struct rspfreasm *re, *rtmp;
  1242. struct mbuf *tbp, *bp1, *bp2;
  1243.  
  1244.     for (re = Rspfreasmq; re != NULLRREASM; re = re->next)
  1245.         if (re->addr == addr) {    /* found another fragment */
  1246.             if (dup_p (&tbp, re->data, 0, RSPFPKTLEN) != RSPFPKTLEN) {
  1247.                 free_p (tbp);
  1248.                 free_p (bp);
  1249.                 return NULLBUF;
  1250.             }
  1251.             (void) ntohrspf (&rspf, &tbp);    /* get its packet header */
  1252.             if (rph->envid != rspf.pkthdr.envid) {
  1253.                 del_reasm (re);    /* an obsolete entry, delete it */
  1254.                 break;
  1255.             }
  1256.             /* Now try to find a place where this fragment fits in the chain */
  1257.             bp1 = re->data;
  1258.             bp2 = NULLBUF;
  1259.             while (rph->fragn > rspf.pkthdr.fragn && bp1->anext != NULLBUF) {
  1260.                 bp2 = bp1;
  1261.                 bp1 = bp1->anext;
  1262.                 if (dup_p (&tbp, bp1, 0, RSPFPKTLEN) != RSPFPKTLEN) {
  1263.                     free_p (bp);
  1264.                     free_p (tbp);
  1265.                     return NULLBUF;
  1266.                 }
  1267.                 (void) ntohrspf (&rspf, &tbp);
  1268.             }
  1269.             if (rspf.pkthdr.fragn == rph->fragn) {
  1270.                 free_p (bp);
  1271.                 return NULLBUF;    /* We already had this one */
  1272.             }
  1273.             bp = htonrspf (rph, bp);    /* Put the packet header back on */
  1274.             /* Insert the fragment at the right place in the chain */
  1275.             if (rph->fragn > rspf.pkthdr.fragn) {
  1276.                 bp1->anext = bp;
  1277.                 bp->anext = NULLBUF;
  1278.             } else {
  1279.                 if (bp2 != NULLBUF)
  1280.                     bp2->anext = bp;
  1281.                 else
  1282.                     re->data = bp;
  1283.                 bp->anext = bp1;
  1284.             }
  1285.             if (len_q (re->data) == rspf.pkthdr.fragtot) {
  1286.                 bp1 = NULLBUF;    /* we have all the fragments */
  1287.                 while ((bp2 = dequeue (&re->data)) != NULLBUF) {
  1288.                     (void) pullup (&bp2, (unsigned char *)0, RSPFPKTLEN);    /* strip the headers */
  1289.                     append (&bp1, bp2);    /* and form a single packet */
  1290.                 }
  1291.                 del_reasm (re);
  1292.                 stop_timer (&Rspfreasmt);
  1293.                 reasmtimeout (NULL);    /* restarts timer if necessary */
  1294.                 return bp1;    /* return the completed packet */
  1295.             }
  1296.             re->time = secclock ();    /* Update the timestamp */
  1297.             goto timstart;    /* We have to wait for fragments */
  1298.         }
  1299.     /* At this point we know that there is no matching entry in the
  1300.        reassembly queue (any more) */
  1301.     if (rph->fragtot == 1)    /* Simple case, an un-fragmented packet */
  1302.         return bp;
  1303.     tbp = htonrspf (rph, bp);    /* Put the packet header back on */
  1304.     rtmp = (struct rspfreasm *) callocw (1, sizeof (struct rspfreasm));
  1305.  
  1306.     /* The values are filled in */
  1307.     rtmp->addr = addr;
  1308.     rtmp->time = secclock ();
  1309.     rtmp->data = tbp;
  1310.     rtmp->next = Rspfreasmq;
  1311.     Rspfreasmq = rtmp;
  1312. timstart:        /* Start the timer if needed */
  1313.     if (!run_timer (&Rspfreasmt)) {
  1314.         Rspfreasmt.func = reasmtimeout;
  1315.         Rspfreasmt.arg = NULL;
  1316.         set_timer (&Rspfreasmt, RSPF_RTIME * 1000L);    /* The reassembly timeout */
  1317.         start_detached_timer (&Rspfreasmt);
  1318.     }
  1319.     return NULLBUF;
  1320. }
  1321.  
  1322.  
  1323.  
  1324. /* Delete a reassembly descriptor from the queue */
  1325. static void
  1326. del_reasm (struct rspfreasm *re)
  1327. {
  1328. struct rspfreasm *r, *prev = NULLRREASM;
  1329.  
  1330.     for (r = Rspfreasmq; r != NULLRREASM; prev = r, r = r->next)
  1331.         if (r == re) {
  1332.             free_q (&re->data);
  1333.             if (prev != NULLRREASM)
  1334.                 prev->next = re->next;
  1335.             else
  1336.                 Rspfreasmq = re->next;
  1337.             free ((char *) re);
  1338.             break;
  1339.         }
  1340. }
  1341.  
  1342.  
  1343.  
  1344. /* When the reassembly timer times out, this function tries to make use of
  1345.  * any fragments in the reassembly queue.
  1346.  */
  1347. static void
  1348. reasmtimeout (void *t OPTIONAL)
  1349. {
  1350. union rspf rspf;
  1351. struct rspfreasm *re;
  1352. struct mbuf *bp, *tbp;
  1353. int last = 0;
  1354. int32 low;
  1355.  
  1356.     re = Rspfreasmq;
  1357.     while (re != NULLRREASM)
  1358.         if ((secclock () - re->time) >= RSPF_RTIME) {
  1359.             /* Try to use what we have */
  1360.             bp = NULLBUF;
  1361.             while ((tbp = dequeue (&re->data)) != NULLBUF) {
  1362.                 (void) ntohrspf (&rspf, &tbp);
  1363.                 if (rspf.pkthdr.fragn != (last + 1)) {    /* a missing fragment */
  1364.                     if (bp != NULLBUF)
  1365.                         update_in (bp, re->addr);
  1366.                     bp = NULLBUF;
  1367.                     if (rspf.pkthdr.sync != 0)
  1368.                         (void) pullup (&tbp, (unsigned char *)0, rspf.pkthdr.sync - 4);
  1369.                     else {    /* no sync possible in this fragment */
  1370.                         free_p (tbp);
  1371.                         continue;
  1372.                     }
  1373.                 }
  1374.                 append (&bp, tbp);
  1375.                 last = rspf.pkthdr.fragn;
  1376.             }
  1377.             if (bp != NULLBUF)
  1378.                 update_in (bp, re->addr);
  1379.             del_reasm (re);
  1380.             re = Rspfreasmq;    /* start over again */
  1381.         } else
  1382.             re = re->next;
  1383.     /* Find the oldest fragment and restart the reassembly timer */
  1384.     low = 0;
  1385.     for (re = Rspfreasmq; re != NULLRREASM; re = re->next)
  1386.         if (re->time < low || low == 0)
  1387.             low = re->time;
  1388.     if (low) {
  1389.         /* KF8NH 1993.01.17: clock() on below line changed to secclock() */
  1390.         set_timer (&Rspfreasmt, (RSPF_RTIME - (secclock () - low)) * 1000L);
  1391.         if (dur_timer (&Rspfreasmt) > 0)    /* just to be safe */
  1392.             start_detached_timer (&Rspfreasmt);
  1393.     }
  1394. }
  1395.  
  1396.  
  1397.  
  1398. /* Handle incoming routing updates (a reassembled envelope) */
  1399. static void
  1400. update_in (
  1401. struct mbuf *bp,        /* Reassembled data packet, without packet header */
  1402. uint32 addr            /* Senders address (in host order) */
  1403. ) {
  1404. struct rspfnodeh nodeh;
  1405. struct rspflinkh linkh;
  1406. struct rspfadj *adj;
  1407. struct mbuf *tbp, *tmp, *b;
  1408. int linkcnt = 0, adjcnt = 0;
  1409. int16 offset = 0;
  1410.  
  1411.     tbp = b = NULLBUF;
  1412.     /* Check to see if the sender is an adjacency */
  1413.     for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  1414.         if (adj->addr == addr)
  1415.             break;
  1416.     /* One may argue that updates from non-adjacencies should not be
  1417.      * accepted since they will not contribute to the routing table.
  1418.      * But it might happen that the sender will very shortly become an
  1419.      * adjacency, and then its routing update will come handy. By increasing
  1420.      * Keeprouter, routing updates from disjoint routers will not be not be
  1421.      * purged when makeroutes() is called this time.
  1422.      */
  1423.     if (adj == NULLADJ) {
  1424.         ++Rspf_stat.noadjupdate;
  1425.         Keeprouter += 2;
  1426.     } else
  1427.         ksignal (adj, 1);    /* alert anyone waiting for the update */
  1428.     while (offset < len_p (bp)) {
  1429.         if (adjcnt) {
  1430.             if (dup_p (&tmp, bp, offset, 5) == 5) {
  1431.                 append (&tbp, tmp);
  1432.                 offset += 5;
  1433.                 adjcnt--;
  1434.                 continue;
  1435.             } else
  1436.                 break;
  1437.         }
  1438.         if (tbp != NULLBUF) {
  1439.             tmp = htonrspflink (&linkh, tbp);
  1440.             append (&b, tmp);
  1441.             tbp = NULLBUF;
  1442.         }
  1443.         if (linkcnt) {
  1444.             if (dup_p (&tbp, bp, offset, RSPFLINKLEN) == RSPFLINKLEN) {
  1445.                 (void) ntohrspflink (&linkh, &tbp);
  1446.                 adjcnt = linkh.adjn;
  1447.                 offset += RSPFLINKLEN;
  1448.                 linkcnt--;
  1449.                 continue;
  1450.             } else
  1451.                 break;
  1452.         }
  1453.         if (b != NULLBUF) {
  1454.             tmp = htonrspfnode (&nodeh, b);
  1455.             node_in (tmp, addr, 1);    /* a full router update */
  1456.             b = NULLBUF;
  1457.         }
  1458.         if (dup_p (&tmp, bp, offset, RSPFNODELEN) == RSPFNODELEN) {
  1459.             (void) ntohrspfnode (&nodeh, &tmp);
  1460.             linkcnt = nodeh.links;
  1461.             offset += RSPFNODELEN;
  1462.         } else {
  1463.             free_p (bp);
  1464.             free_p (tmp);
  1465.             return;
  1466.         }
  1467.     }
  1468.     if (tbp != NULLBUF) {
  1469.         /* adjust the adjacency counter in the link header */
  1470.         linkh.adjn -= uchar(adjcnt);    /*lint !e644 */
  1471.         tmp = htonrspflink (&linkh, tbp);
  1472.         append (&b, tmp);
  1473.     }
  1474.     /* adjust the link counter in the node header */
  1475.     nodeh.links -= uchar(linkcnt);        /*lint !e771 */
  1476.     tmp = htonrspfnode (&nodeh, b);
  1477.     free_p (bp);
  1478.     if (linkcnt || adjcnt)
  1479.         node_in (tmp, addr, 0);    /* a partial router update */
  1480.     else
  1481.         node_in (tmp, addr, 1);
  1482. }
  1483.  
  1484.  
  1485.  
  1486. static void
  1487. node_in (
  1488. struct mbuf *bp,        /* A single update, starting with the node header */
  1489. uint32 addr,            /* Address of station we got packet from */
  1490. int full            /* False if we got a partial update */
  1491. ) {
  1492. struct mbuf *tbp;
  1493. struct rspfnodeh nodeh, rnodeh;
  1494. struct rspfrouter *rr;
  1495.  
  1496.     if (dup_p (&tbp, bp, 0, RSPFNODELEN) != RSPFNODELEN) {
  1497.         free_p (bp);
  1498.         free_p (tbp);
  1499.         return;
  1500.     }
  1501.     (void) ntohrspfnode (&nodeh, &tbp);
  1502.     if (ismyaddr (nodeh.addr)) {
  1503.         /* If another station thinks our routing update sequence number is
  1504.          * larger than it really is, this might be because we have had
  1505.          * a fast system reset and routing updates from the old "epoch"
  1506.          * are still present in the network.
  1507.          */
  1508.         if (isnewer (nodeh.seq, Rspfseq)) {
  1509.             Rspfseq = nodeh.seq + 1;    /* Catch up */
  1510.             if (nodeh.seq == 32768L - 2 || nodeh.seq == -32768L + 1)
  1511.                 Rspfseq = 0;    /* Wrap around */
  1512.             sendonerspf (nodeh.addr, addr);    /* Send him the latest packet */
  1513.         }
  1514.         free_p (bp);    /* We already know our own adjacencies! */
  1515.         return;
  1516.     }
  1517.     if ((rr = rr_lookup (nodeh.addr)) != NULLRROUTER) {
  1518.         if (dup_p (&tbp, rr->data, 0, RSPFNODELEN) != RSPFNODELEN) {
  1519.             free_p (bp);
  1520.             free_p (tbp);
  1521.             return;
  1522.         }
  1523.         (void) ntohrspfnode (&rnodeh, &tbp);
  1524.         if (nodeh.seq == rnodeh.seq && nodeh.subseq <= uchar(rr->subseq)) {
  1525.             free_p (bp);
  1526.             return;    /*  We already have this one */
  1527.         }
  1528.         if (isnewer (rnodeh.seq, nodeh.seq)) {
  1529.             /* Send him the latest packet */
  1530.             sendonerspf (nodeh.addr, addr);
  1531.             free_p (bp);
  1532.             ++Rspf_stat.oldreport;
  1533.             return;
  1534.         }
  1535.         if (nodeh.subseq > uchar(rr->subseq) && nodeh.seq == rnodeh.seq) {
  1536.             rr->subseq = (char) nodeh.subseq;
  1537.             partialupdate (rr, bp);
  1538.             makeroutes ();
  1539.             return;
  1540.         }
  1541.         if (isnewer (nodeh.seq, rnodeh.seq) && !full) {
  1542.             partialupdate (rr, bp);
  1543.             makeroutes ();
  1544.             /* Send a "poll" packet */
  1545.             --nodeh.seq;
  1546.             nodeh.subseq = 0;
  1547.             nodeh.links = 0;
  1548.             tbp = htonrspfnode (&nodeh, NULLBUF);
  1549.             sendupdate (tbp, 1, addr);
  1550.             ++Rspf_stat.outpolls;
  1551.             return;
  1552.         }
  1553.     } else {
  1554.         rr = (struct rspfrouter *) callocw (1, sizeof (struct rspfrouter));
  1555.  
  1556.         rr->next = Rspfrouters;
  1557.         Rspfrouters = rr;
  1558.     }
  1559.     free_p (rr->data);
  1560.     rr->data = bp;
  1561.     rr->subseq = (char) nodeh.subseq;
  1562.     rr->time = secclock ();
  1563.     rr->sent = 0;
  1564.     makeroutes ();
  1565.     return;
  1566. }
  1567.  
  1568.  
  1569.  
  1570. /* Return the matching RSPF route entry for addr (in host order) */
  1571. static struct rspfrouter *
  1572. rr_lookup (uint32 addr)
  1573. {
  1574. struct rspfrouter *rr;
  1575.  
  1576.     for (rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next)
  1577.         /* this assumes that the first word of the header is the address */
  1578.         if (rr->data != NULLBUF && get32 ((char *) rr->data->data) == addr)
  1579.             return rr;
  1580.     return NULLRROUTER;
  1581. }
  1582.  
  1583.  
  1584.  
  1585. /* Delete the route entry for address addr */
  1586. static void
  1587. rr_delete (uint32 addr)
  1588. {
  1589. struct rspfrouter *rr, *prev = NULLRROUTER;
  1590.  
  1591.     for (rr = Rspfrouters; rr != NULLRROUTER; prev = rr, rr = rr->next)
  1592.         /* this assumes that the first word of the header is the address */
  1593.         if (rr->data != NULLBUF && get32 ((char *) rr->data->data) == addr) {
  1594.             if (prev != NULLRROUTER)
  1595.                 prev->next = rr->next;
  1596.             else
  1597.                 Rspfrouters = rr->next;
  1598.             free_p (rr->data);
  1599.             free ((char *) rr);
  1600.             return;
  1601.         }
  1602. }
  1603.  
  1604.  
  1605.  
  1606. /* Handle incoming partial routing updates. Adjacencies from bp will be
  1607.  * merged into rr->data
  1608.  */
  1609. static void
  1610. partialupdate (
  1611. struct rspfrouter *rr,        /* current node entry in routing table */
  1612. struct mbuf *bp            /* data packet, starting with node header */
  1613. ) {
  1614. struct rspflinkh linkh, rlinkh;
  1615. struct rspfnodeh rnodeh;
  1616. struct mbuf *wbp, *tbp, *tmp, *b;
  1617. int adjcnt = 0, radjcnt, rlinkcnt = 0, bits, rbits, added = 0;
  1618. uint32 addr, raddr;
  1619.  
  1620.     rlinkh.adjn = 0;
  1621.     rr->time = secclock ();
  1622.     rr->sent = 0;
  1623.     /* Make a working copy of the stored routing update */
  1624.     if (dup_p (&wbp, rr->data, 0, len_p (rr->data)) != len_p (rr->data)) {
  1625.         free_p (wbp);
  1626.         free_p (bp);
  1627.         return;
  1628.     }
  1629.     (void) ntohrspfnode (&rnodeh, &wbp);
  1630.     (void) pullup (&bp, (unsigned char *)0, RSPFNODELEN);    /* Strip off the node header */
  1631.     while (len_p (bp) > 0)
  1632.         if (adjcnt == 0) {
  1633.             if (ntohrspflink (&linkh, &bp) == -1) {
  1634.                 free_p (wbp);
  1635.                 free_p (bp);
  1636.                 return;
  1637.             }
  1638.             adjcnt = linkh.adjn;
  1639.         } else {
  1640.             bits = PULLCHAR (&bp);    /*lint !e506 * get one adjacency to merge */
  1641.             if (pullup (&bp, (unsigned char *) &addr, 4) != 4) {
  1642.                 free_p (wbp);
  1643.                 free_p (bp);
  1644.                 return;
  1645.             }
  1646.             addr = get32 ((char *) &addr);    /* convert to host order */
  1647.             --adjcnt;
  1648.             radjcnt = 0;
  1649.             b = tbp = NULLBUF;
  1650.             for ( ; ; ) {    /* search through stored update */
  1651.                 if (radjcnt == 0 || len_p (wbp) == 0) {
  1652.                     if (tbp != NULLBUF) {
  1653.                         rlinkh.adjn -= uchar(radjcnt);
  1654.                         tmp = htonrspflink (&rlinkh, tbp);
  1655.                         ++rlinkcnt;
  1656.                         append (&b, tmp);
  1657.                         tbp = NULLBUF;
  1658.                     }
  1659.                     if (len_p (wbp) == 0)
  1660.                         break;
  1661.                 }
  1662.                 if (radjcnt == 0) {
  1663.                     (void) ntohrspflink (&rlinkh, &wbp);
  1664.                     radjcnt = rlinkh.adjn;
  1665.                     if (rlinkh.horizon == linkh.horizon && rlinkh.cost ==
  1666.                         linkh.cost && rlinkh.erp == linkh.erp) {    /*lint !e644 */
  1667.                         pushadj (&tbp, addr, bits);
  1668.                         ++rlinkh.adjn;
  1669.                         added = 1;
  1670.                     }
  1671.                 } else {
  1672.                     rbits = PULLCHAR (&wbp);        /*lint !e506 */
  1673.                     raddr = pull32 (&wbp);
  1674.                     --radjcnt;
  1675.                     if (bits != rbits || addr != raddr)
  1676.                         pushadj (&tbp, raddr, rbits);    /* Put it back */
  1677.                     else
  1678.                         --rlinkh.adjn;    /* deleted one adjacency */
  1679.                 }
  1680.             }
  1681.             wbp = b;/* wbp now keeps link headers and adjacencies */
  1682.             if (linkh.cost < 255 && !added) {    /* Append the new link */
  1683.                 ++rnodeh.links;    /* We will add one extra link */
  1684.                 tmp = ambufw (5);
  1685.                 *tmp->data = uchar(bits);
  1686.                 (void) put32 (tmp->data + 1, addr);
  1687.                 tmp->cnt = tmp->size;
  1688.                 tbp = htonrspflink (&linkh, tmp);
  1689.                 append (&wbp, tbp);
  1690.             }
  1691.             added = 0;
  1692.         }
  1693.     free_p (rr->data);
  1694.     rnodeh.links = uchar(rlinkcnt);
  1695.     rr->data = htonrspfnode (&rnodeh, wbp);
  1696. }
  1697.  
  1698.  
  1699.  
  1700. /* The shortest path first algorithm */
  1701. static void
  1702. makeroutes (void)
  1703. {
  1704. int bits, i, low, adjcnt;
  1705. struct mbuf *bp;
  1706. struct route *rp, *rp2, *saved[HASHMOD];
  1707. struct rspfadj *adj, *lowadj, *gateway = (struct rspfadj *)0;
  1708. unsigned char *lowp, *r;
  1709. uint32 lowaddr;
  1710. struct rspflinkh linkh;
  1711. struct rspfrouter *rr, *rrprev;
  1712.  
  1713.     if (Keeprouter)        /* if false, purge unreachable router entries */
  1714.         --Keeprouter;
  1715.     /* Before we change anything in the routing table, we have to save
  1716.      * each local adjacencies riface pointer
  1717.      */
  1718.     for (adj = Adjs; adj != NULLADJ; adj = adj->next)
  1719.         adj->scratch = (void *) rtif_lookup (adj->addr);
  1720.     /* Remove all non-manual routes */
  1721.     for (bits = 1; bits <= 32; bits++)
  1722.         for (i = 0; i < HASHMOD; i++)
  1723.             for (rp = Routes[bits - 1][i]; rp != NULLROUTE; rp = rp2) {
  1724.                 rp2 = rp->next;    /* BIG BUG FIX -- sm6rpz */
  1725.                 if (dur_timer (&rp->timer) != 0)
  1726.                     (void) rt_drop (rp->target, (unsigned) bits);
  1727.                 /* rp will be undefined here if(dur_timer(&rp->timer) */
  1728.             }
  1729.     if (rp)
  1730.         (void) rt_drop (rp->target, (unsigned) bits);
  1731.  
  1732.     if ((rp = rt_blookup (0, 0)) != NULLROUTE && dur_timer (&rp->timer) != 0)
  1733.         (void) rt_drop (0, 0);    /* delete non-manual default route */
  1734.  
  1735.     /* Temporarily remove all 32-bit specific manual routes. This will make
  1736.      * it possible to prevent loops in findlowroute()
  1737.      */
  1738.     for (i = 0; i < HASHMOD; i++) {
  1739.         saved[i] = Routes[31][i];
  1740.         Routes[31][i] = NULLROUTE;
  1741.     }
  1742.  
  1743.     for ( ; ; ) {
  1744.         lowadj = NULLADJ;
  1745.         lowp = (unsigned char *)0;
  1746.         low = 255;
  1747.         for (adj = Adjs; adj != NULLADJ; adj = adj->next) {
  1748.             if (adj->scratch == NULL)
  1749.                 continue;    /* skip unreachable adjacency */
  1750.             if (!adj->added) {
  1751.                 if (adj->cost <= low) {
  1752.                     low = adj->cost;
  1753.                     lowadj = adj;
  1754.                     lowp = (unsigned char *)0;
  1755.                 }
  1756.             } else if ((r = (unsigned char *) findlowroute (adj->addr, &low, adj->cost, &lowaddr, &bits))
  1757.                    != (unsigned char *)0) {
  1758.                 lowp = r;
  1759.                 gateway = adj;
  1760.                 lowadj = NULLADJ;
  1761.             }
  1762.         }
  1763.         if (lowadj != NULLADJ) {
  1764.             lowadj->added++;
  1765.             rp = rt_add (lowadj->addr, 32, 0,
  1766.                   ((struct rspfiface *) lowadj->scratch)->iface,
  1767.                      (int32) lowadj->cost, 0, 0);
  1768.             /* set the timer to a dummy value. This makes it possible to
  1769.              * distinguish between manual and RSPF-generated routes.
  1770.              * The timer is never started however since RSPF handles the
  1771.              * expiration of routes itself.
  1772.              */
  1773.             if (rp)
  1774.                 set_timer (&rp->timer, MSPTICK);
  1775.             continue;
  1776.         }
  1777.         if (lowp != (unsigned char *)0) {
  1778.             /* Check if we already have this one */
  1779.             rp = rt_blookup (lowaddr, (unsigned) bits);    /*lint !e644 */
  1780.             if ((rp == NULLROUTE || (rp != NULLROUTE &&
  1781.             rp->metric > (int32) low)) && !ismyaddr (lowaddr)) {
  1782.                 /* This is a new route, or a route with strict lower cost than
  1783.                  * the previous route (possible only if it was manual)
  1784.                  */
  1785.                 if (gateway)
  1786.                     rp = rt_add (lowaddr, (unsigned) bits, gateway->addr,
  1787.                         ((struct rspfiface *) gateway->scratch)->iface,
  1788.                         (int32) low, 0, 0);
  1789.                 if (rp)
  1790.                     set_timer (&rp->timer, MSPTICK);    /* a dummy value */
  1791.             }
  1792.             *lowp |= 128;    /* mark the route as added in any case */
  1793.         } else
  1794.             break;    /* no more routes */
  1795.     }
  1796.  
  1797.     /* Add the saved 32 bit routes, if there isn't now a better route */
  1798.     for (i = 0; i < HASHMOD; i++) {
  1799.         rp = saved[i];
  1800.         while (rp != NULLROUTE) {
  1801.             rp2 = rt_blookup (rp->target, 32);
  1802.             if (rp2 == NULLROUTE || (rp2 != NULLROUTE && rp2->metric >= rp->metric)) {
  1803.                 rp2 = rt_add (rp->target, 32, rp->gateway, rp->iface, rp->metric,
  1804.                           0, rp->flags & RTPRIVATE);
  1805.                 rp2->uses = rp->uses;
  1806.             }
  1807.             rp2 = rp->next;
  1808.             stop_timer (&rp->timer);    /* Stop timer before free() -- KZ1F */
  1809.             free ((char *) rp);
  1810.             rp = rp2;
  1811.         }
  1812.     }
  1813.  
  1814.     /* Reset all flags */
  1815.     for (adj = Adjs; adj != NULLADJ; adj = adj->next) {
  1816.         adj->added = 0;
  1817.         adj->scratch = NULL;
  1818.     }
  1819.  
  1820.     for (rr = Rspfrouters; rr != NULLRROUTER; rr = rr->next) {
  1821.         i = len_p (rr->data) - RSPFNODELEN;
  1822.         /* jump past the node header */
  1823.         if (dup_p (&bp, rr->data, RSPFNODELEN, (int16) i) != i) {
  1824.             free_p (bp);
  1825.             continue;
  1826.         }
  1827.         adjcnt = 0;
  1828.         while (i > 0) {
  1829.             if (adjcnt) {
  1830.                 if (!Keeprouter && (*bp->data & 128) == 0) {
  1831.                     /* This router has an adjacency that was not added. That
  1832.                      * means that the router is unreachable. Mark the
  1833.                      * stored routing update for deletion.
  1834.                      */
  1835.                     free_p (bp);
  1836.                     free_p (rr->data);
  1837.                     rr->data = NULLBUF;    /* indicates disposal */
  1838.                     break;
  1839.                 }
  1840.                 *bp->data &= ~128;    /* Clear the "added" bit */
  1841.                 (void) pullup (&bp, (unsigned char *)0, 5);
  1842.                 i -= 5;
  1843.                 --adjcnt;
  1844.                 continue;
  1845.             }
  1846.             (void) ntohrspflink (&linkh, &bp);
  1847.             adjcnt = linkh.adjn;
  1848.             i -= RSPFLINKLEN;
  1849.         }
  1850.     }
  1851.  
  1852.     if (Keeprouter)        /* nothing more to do */
  1853.         return;
  1854.     /* Delete any routers that were discovered as being unreachable */
  1855.     rrprev = NULLRROUTER;
  1856.     rr = Rspfrouters;
  1857.     for ( ; ; ) {
  1858.         for (rrprev = NULLRROUTER, rr = Rspfrouters; rr != NULLRROUTER;
  1859.              rrprev = rr, rr = rr->next)
  1860.             if (rr->data == NULLBUF) {
  1861.                 if (rrprev != NULLRROUTER)
  1862.                     rrprev->next = rr->next;
  1863.                 else
  1864.                     Rspfrouters = rr->next;
  1865.                 free ((char *) rr);
  1866.                 break;
  1867.             }
  1868.         if (rr == NULLRROUTER)
  1869.             break;
  1870.     }
  1871. }
  1872.  
  1873.  
  1874.  
  1875. /* Find a route from addr with the lowest cost. Returns a pointer to the
  1876.  * buffer that keeps the significant bit count of the selected route.
  1877.  */
  1878. static char *
  1879. findlowroute (
  1880. uint32 addr,            /* The node whose routes will be examined */
  1881. int *low,            /* Lowest cost so far */
  1882. int add,            /* Cost of this node */
  1883. uint32 *resaddr,        /* Resulting route stored here */
  1884. int *resbits            /* Significant bits of resulting route */
  1885. ) {
  1886. struct mbuf *bp;
  1887. struct rspfrouter *rr;
  1888. struct rspflinkh linkh;
  1889. struct route *rp;
  1890. char *r, *retval = NULLCHAR;
  1891. int adjcnt = 0;
  1892.  
  1893.     linkh.cost = 0;
  1894.     if ((rr = rr_lookup (addr)) == NULLRROUTER)
  1895.         return NULLCHAR;
  1896.     if ((rp = rt_blookup (addr, 32)) != NULLROUTE && rp->metric < add)
  1897.         return NULLCHAR;/* already added this one, no loops thanks */
  1898.     if (dup_p (&bp, rr->data, RSPFNODELEN, len_p (rr->data) - RSPFNODELEN) !=
  1899.         len_p (rr->data) - RSPFNODELEN) {
  1900.         free_p (bp);
  1901.         return NULLCHAR;
  1902.     }
  1903.     while (len_p (bp) > 0) {
  1904.         if (adjcnt) {
  1905.             if (*bp->data & 128) {
  1906.                 (void) PULLCHAR (&bp);    /*lint !e506 */
  1907.                 if ((r = findlowroute (pull32 (&bp), low, add + linkh.cost, resaddr,
  1908.                                resbits)) != NULLCHAR)
  1909.                     retval = r;
  1910.             } else {
  1911.                 *low = add + linkh.cost;
  1912.                 retval = (char *) bp->data;
  1913.                 *resbits = PULLCHAR (&bp);    /*lint !e506 */
  1914.                 *resaddr = pull32 (&bp);
  1915.                 (void) pullup (&bp, (unsigned char *)0, (int16) (5 * (adjcnt - 1)));
  1916.                 adjcnt = 1;    /* No need to check the rest of this link */
  1917.             }
  1918.             --adjcnt;
  1919.             continue;
  1920.         }
  1921.         (void) ntohrspflink (&linkh, &bp);
  1922.         if ((add + linkh.cost) <= *low)
  1923.             adjcnt = linkh.adjn;
  1924.         else
  1925.             (void) pullup (&bp, (unsigned char *)0, 5 * linkh.adjn);
  1926.     }
  1927.     return retval;
  1928. }
  1929.  
  1930.  
  1931.  
  1932. #ifndef    AX25
  1933. /*
  1934.  * Dummy stub for RSPF if AX25 is not configured.
  1935.  */
  1936. static struct lq *
  1937. al_lookup (struct iface *ifp, char *addr, int sort)
  1938. {
  1939.     return NULLLQ;
  1940. }
  1941. #endif /* AX25 */
  1942.  
  1943. #endif /* RSPF */
  1944.